/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

import java.util.*;

/**
 *
 * @author me
 */
public class AcademicPlan {

    public static ClassUnitPair[] ArrayInterleave(ClassUnitPair[][] arrays) {
        int numArrays = arrays.length;
        int totalClasses = 0;
        for(int i=0;i<arrays.length;i++) {
            totalClasses += arrays[i].length;
        }
        ClassUnitPair[] interleaved = new ClassUnitPair[totalClasses];
        int[] indices = new int[numArrays];
        for(int i=0;i<numArrays;i++)
            indices[i] = 0;

        int oi = 0;     // output index;
        int i = 0;      // which array is currently retrieved.
        
        while(true) {
            int j;
            for(j=0;j<numArrays;j++) {    // forward to an array that has more elements
                if(indices[i] < arrays[i].length)
                    break;
                i = (++i)%numArrays;
            }

            if(j>=numArrays)    // no array has more element. exit.
                break;

            interleaved[oi++] = arrays[i][indices[i]++];
            i = (++i)%numArrays;
        }
        return interleaved;
    }

    /**
     * Get a scheduling by having the core, support, GE classes go first before
     *  going into electives
     *
     * Assuming units are all positive values.
     * Assume there's no duplicated value in the class lists
     * 
     * @param cores
     * @param cUnits
     * @param supports
     * @param sUnits
     * @param ges
     * @param gUnits
     * @param electives
     * @param eUnits
     * @param maxQuarterlyUnits
     * @return  The academic plan is an ArrayList of ArrayList of strings.
     *          (Each ArrayList at the sub level a plan for the next quarter.
     *
     * @throws Exception
     */
    public static ArrayList getScheduleElectiveLast(String[] cores, int[] cUnits,
                                        String[] supports, int[] sUnits,
                                        String[] ges, int[] gUnits,
                                        String[] electives, int[] eUnits,
                                        int maxQuarterlyUnits) throws Exception
    {
        Exception ex = new Exception("Max quarterly units limit is below units required for some class.");
        for(int i=0;i<cUnits.length;i++)
            if(cUnits[i] > maxQuarterlyUnits) {
                throw ex;
            }
        for(int i=0;i<sUnits.length;i++)
            if(sUnits[i] > maxQuarterlyUnits) {
                throw ex;
            }
        for(int i=0;i<gUnits.length;i++)
            if(gUnits[i] > maxQuarterlyUnits) {
                throw ex;
            }
        for(int i=0;i<eUnits.length;i++)
            if(eUnits[i] > maxQuarterlyUnits) {
                throw ex;
            }

        ClassUnitPair[] coreArray = ClassUnitPair.makeArray(cores, cUnits);
        ClassUnitPair[] supportArray = ClassUnitPair.makeArray(supports, sUnits);
        ClassUnitPair[] geArray = ClassUnitPair.makeArray(ges, gUnits);
        ClassUnitPair[] electiveArray = ClassUnitPair.makeArray(electives, eUnits);

        ClassUnitPair[][] first3 = {coreArray, supportArray, geArray};
        ClassUnitPair[] mixed = ArrayInterleave(first3);

        for(int i=0;i<mixed.length;i++)
            System.out.print(mixed[i].classId + " " );
        System.out.println();

        String electiveBeginClass = null;  // the last (core/support) class before elective can begin
        if(coreArray.length > supportArray.length) {
            if(coreArray.length>0)
                electiveBeginClass = coreArray[coreArray.length-1].classId;
        } else {
            if(supportArray.length>0)
                electiveBeginClass = supportArray[supportArray.length-1].classId;
        }

        ArrayList list = new ArrayList(mixed.length);
        for(int i=0;i<mixed.length;i++) {
            list.add(mixed[i]);
        }

        int j;
        for(j=mixed.length-1;j>=0;j--) {
            if(mixed[j].classId.compareTo(electiveBeginClass) == 0)
                break;
        }

System.out.println("j=" +j);
        if(j==mixed.length-1) {
            for(int i=0;i<electiveArray.length;i++)
                list.add(electiveArray[i]);
        } else {
            ArrayList preList = new ArrayList( list.subList(0, j+1) );
            ArrayList postList = new ArrayList(list.subList(j+1, list.size()));
            ClassUnitPair[] remainingGE = new ClassUnitPair[postList.size()];
            for(int i=0;i<postList.size();i++)
                remainingGE[i] = (ClassUnitPair) postList.get(i);
            ClassUnitPair[][] remainings = {remainingGE, electiveArray};
            mixed = ArrayInterleave(remainings);
            ArrayList mixedList = new ArrayList();
            for(int i=0;i<mixed.length;i++)
                mixedList.add(mixed[i]);
            list = preList;
            list.addAll(mixedList);
        }

        // Now, variable list stores a all the classes interleaved, with
        // core and support classes go first before getting into electives
        // Seperate them into arrays by maximum units 
        ArrayList retVal = new ArrayList();
        ArrayList quarterList = new ArrayList();
        int units = 0;
        for(int i=0;i<list.size();i++) {
            ClassUnitPair cup = (ClassUnitPair) list.get(i);
            if(units + cup.units > maxQuarterlyUnits) {
                units = 0;
                retVal.add(quarterList);
                quarterList = new ArrayList();
            }
            quarterList.add(cup);
            units += cup.units;
        }
        if(quarterList.size()>0)
            retVal.add(quarterList);
        return retVal;
    }

    public static void main(String[] args) throws Exception {
        String[] cores = {};
        int[] cUnits = {};
        String[] supports = {"Support1", "Support2", "Support3", "Support4"};
        int[] sUnits = {4,4,4,4};
        String[] ges = {"GE1", "GE2"};
        int[] gUnits = {4,4};
        String[] electives = {"Elective1", "Elective2", "Elective3", "Elective4"};
        int[] eUnits = {4,4,4,4};

        ArrayList list = AcademicPlan.getScheduleElectiveLast(cores, cUnits,
                                        supports, sUnits,
                                        ges, gUnits,
                                        electives, eUnits,
                                        16);
        for(int i=0;i<list.size();i++) {
            ArrayList quarter = (ArrayList) list.get(i);
            System.out.println("------------");
            System.out.println("Quarter:");

            for(int j=0;j<quarter.size();j++) {
                ClassUnitPair cup = (ClassUnitPair) quarter.get(j);
                System.out.println(cup.classId + " " + cup.units);
            }
        }
    }
 
}


class ClassUnitPair{
    public String classId;
    public int units;
    public ClassUnitPair(String classId, int units) {
        this.classId = classId;
        this.units = units;
    }

    public static ClassUnitPair[] makeArray(String[] classList, int[] unitsList) throws Exception{
        if(classList.length != unitsList.length)
            throw new Exception("The number of classes and the provided items for units do not match.");
        int s = classList.length;
        ClassUnitPair[] retVal = new ClassUnitPair[s];
        for(int i=0;i<s;i++) {
            retVal[i] = new ClassUnitPair(classList[i], unitsList[i]);
        }
        return retVal;
    }
}